package com.algorithm.sort.heap;

/**
 * 堆排序
 * 构建大顶堆
 * 在Java中堆的实现是优先级队列
 *
 * @program: sudy
 * @className: HeapSort
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-02-05 15:29
 **/
public class HeapSort {

    /**
     * 数据存放，从index=1开始存放
     */
    private int[] data;
    /**
     * 当前已经存放了多少
     */
    private int count;
    /**
     * 最大容量
     */
    private int n;

    public static void main(String[] args) {
        int[] array = {1, 2, 6, 5, 7, 8, 33, 4, 21, 17, 13, 16, 15, 9};
        HeapSort heapSort = new HeapSort(array);
        for (int n : array) {
            heapSort.insert(n);
        }

        for (int n : heapSort.data) {
            System.out.println(n);
        }

//        System.out.println("***************************************************");
//        heapSort.removeMax();
//        for (int n : heapSort.data) {
//            System.out.println(n);
//        }

        heapSort.sort();
        System.out.println("***************************************************");
        for (int n : heapSort.data) {
            System.out.println(n);
        }



    }

    /**
     * @param n: 堆的最大容量
     * @method:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 15:47
     * @modify_user:TODO
     * @modify_time: 2020/2/5 15:47
     **/
    public HeapSort(int n) {
        this.n = n;
        this.count = 0;
        this.data = new int[n + 1];
    }

    /**
     * @method:
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 16:53
     * @modify_user:TODO
     * @modify_time: 2020/2/5 16:53
     **/
    public HeapSort(int[] data) {
        this.n = data.length;
        this.count = 0;
        this.data = new int[this.n + 1];
        for (int i = 0; i < data.length; ++i) {
            this.data[i + 1] = data[i];
        }
    }

    /**
    * @method: 堆排序主要分两个阶段
     * 1. 创建堆
     * 2. 排序
    * @param:
    * @return:
    * @author: kukuxiahuni
    * @create: 2020/2/5 18:41
    * @modify_user:TODO
    * @modify_time: 2020/2/5 18:41
    **/
    public final void sort() {
        this.buildHeap();
        int k = this.n;

        while (k >= 1) {
            /**
             * 将最大值交换到数组末尾
             */
            swap(this.data, 1, k);
            /**
             * 对1-k-1的数据进行堆化
             */
            --k;
            this.heapify(this.data, k, 1);
        }
    }

    /**
     * @method: 构建堆
     * 1. 直接原地构建堆
     * 2. 从第一个非叶子节点开始不断向下重建堆
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 16:50
     * @modify_user:TODO
     * @modify_time: 2020/2/5 16:50
     **/
    public final void buildHeap() {

        for (int i = this.n / 2; i >= 1; --i) {
            this.heapify(this.data, this.n, i);
        }

    }



    /**
     * @method: 向堆尾插入元素
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 15:47
     * @modify_user:TODO
     * @modify_time: 2020/2/5 15:47
     **/
    public boolean insert(int value) {
        if (count >= n) {
            //堆已经满了
            return false;
        }
        /**
         * 注意count从1开始
         */
        ++count;
        /**
         * 将数据放在堆的最后
         */
        data[count] = value;
        /**
         * 从低往上构建堆
         */

        int i = count;
        /**
         * 大顶堆
         * 1、 父节点存在
         * 2. 父节点(i/2)小于子节点值
         */
        while (i / 2 > 0 && data[i] > data[i / 2]) {
            swap(data, i, i / 2);
            i = i / 2;
        }

        return true;

    }

    /**
     * @method: 删除最大值
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 16:50
     * @modify_user:TODO
     * @modify_time: 2020/2/5 16:50
     **/
    public void removeMax() {
        if (count == 0) {
            return;
        }

        //将最大值替换为a[count]的值
        this.data[1] = this.data[count];
        this.data[count] = 0; //抹掉该位置的值
        --count;
        this.heapify(this.data, count, 1);

    }

    /**
     * @param n:数组的最大容量位置
     * @param i:          堆开始堆化的地方
     * @param data: 堆
     * @param n : 堆的大小
     * @method: 自顶向下堆化
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 16:12
     * @modify_user:TODO
     * @modify_time: 2020/2/5 16:12
     **/
    private final void heapify(int[] data, int n, int i) {
        while (true) {
            //找到i的最大孩子位置
            int maxPos = i;
            if (2 * i <= n && data[maxPos] < data[2 * i]) {
                maxPos = 2 * i;
            }

            if (2 * i + 1 <= n && data[maxPos] < data[2 * i + 1]) {
                maxPos = 2 * i + 1;
            }

            //不需要交换
            if (maxPos == i) {
                break;
            }

            swap(data, i, maxPos);
            i = maxPos;
        }
    }

    /**
     * @method: 数组数据交换
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 15:44
     * @modify_user:TODO
     * @modify_time: 2020/2/5 15:44
     **/
    private final void swap(int[] data, int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }

}
